package com.nanbei.queue;

/**
 * @ClassDescription: 大顶堆
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/11/29 14:17
 */
public class HeapQueue<E extends Priority> implements QueueInterface<E> {


    Priority[] array;
    int size;

    public HeapQueue(int capacity) {
        this.array = new Priority[capacity];
    }


    /**
     * 先将待插入的节点插入树的尾部，在将插入的节点与父节点进行比较
     * 如果比父节点大就 交换父节点和子节点的位置 直到父节点的值大于子节点的值
     * 如果比父节点小就插入成功
     * <p>
     * - 节点 i 的父节点为 floor((i-1)/2)，当 i>0 时
     * - 节点 i 的左子节点为 2i+1，右子节点为 2i+2，当然它们得 < size
     *
     * @param value 待插入值
     * @return 是否插入成功
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int chard = size++;
        int parent = (size - 1) / 2;
        while (chard > 0 && array[chard].getPriority() > array[parent].getPriority()) {
            array[chard] = array[parent];
            chard = parent;
            parent = (chard - 1) / 2;
        }
        array[chard] = value;
        return true;
    }

    /**
     * 先将堆的根节点和最后的叶子节点进行位置交换
     * 交换以后比较 根节点的值较小 开始下潜
     * 下潜：
     *      比较该节点的左孩子和右孩子  哪个还在较大 然后交换位置 直到该节点下潜到最后
     *
     * @return 是否删除成功
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        changeValue(0, size - 1);
        E priority = (E)array[size - 1];
        array[--size] = null;

        shiftDown(0);

        return (E) priority;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    public void changeValue(int start, int target) {
        Priority priority = array[start];
        array[start] = array[target];
        array[target] = priority;
    }

    /**
     * 下潜
     *  假设当前节点的值最大：
     *      然后与左孩子和右孩子进行比较 当左右孩子比当前节点的值大时，交换当前节点和孩子最大值的节点
     *      只有当 max 在进行比较完成一会后发现没有改变则证明孩子的节点没有比当前节点的值大的 则证明下潜完毕。
     *
     *
     * @param parent 父节点的下标
     */
    void shiftDown(int parent) {
        int left = 2*parent +1;
        int right = left+1;
        int max = parent;

        if (left <size && array[left].getPriority() > array[max].getPriority()){
            max = left;
        }
        if (right< size && array[right].getPriority() > array[max].getPriority()){
            max = right;
        }
        if (max != parent){
            changeValue(max,parent);
            shiftDown(max);

        }
    }


}
